# 37. 解数独
# 编写一个程序，通过填充空格来解决数独问题。
#
# 数独的解法需 遵循如下规则：
#
# 数字 1-9 在每一行只能出现一次。
# 数字 1-9 在每一列只能出现一次。
# 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
# 数独部分空格内已填入了数字，空白格用 '.' 表示。
#
#
#
# 示例：
#
#
# 输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
# 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
# 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
#
#
#
#
# 提示：
#
# board.length == 9
# board[i].length == 9
# board[i][j] 是一位数字或者 '.'
# 题目数据 保证 输入数独仅有一个解
from copy import deepcopy
from typing import List


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        p = []
        to_complete = []
        for i in range(9):
            line = [set(range(1, 10)) for _ in range(9)]
            for j in range(9):
                if board[i][j] != '.':
                    line[j] = {int(board[i][j])}
                else:
                    to_complete.append((i, j))
            p.append(line)

        def relax(_p, i: int, j: int):
            ss = _p[i][j]
            if len(ss) == 0:
                return -1
            if len(ss) == 1:
                return 0
            size = len(ss)
            for k in range(9):
                if k == j:
                    continue
                if len(_p[i][k]) == 1:
                    ss -= _p[i][k]
                    if len(ss) == 0:
                        return -1
            for k in range(9):
                if k == i:
                    continue
                if len(_p[k][j]) == 1:
                    ss -= _p[k][j]
                    if len(ss) == 0:
                        return -1

            mat_i = i // 3 * 3
            mat_j = j // 3 * 3
            for k1 in range(mat_i, mat_i + 3):
                for k2 in range(mat_j, mat_j + 3):
                    if k1 == i and k2 == j:
                        continue
                    if len(_p[k1][k2]) == 1:
                        ss -= _p[k1][k2]
            if len(ss) == 0:
                return -1
            return size - len(ss)

        def relax_all(_p):
            cost = 1
            while cost > 0:
                c = 0
                for i in range(9):
                    for j in range(9):
                        x = relax(_p, i, j)
                        if x >= 0:
                            c += x
                        else:
                            c = -abs(c)
                cost = c
            return cost

        relax_all(p)

        def find_dp(_tmp_p):
            choice = None
            choice_i = None
            choice_j = None
            for i in range(9):
                for j in range(9):
                    if choice is None and len(_tmp_p[i][j]) > 1:
                        choice = _tmp_p[i][j]
                        choice_i = i
                        choice_j = j
            if choice is None:
                return _tmp_p

            for elem in choice:
                pp = deepcopy(_tmp_p)
                pp[choice_i][choice_j] = {elem}
                cc = relax_all(pp)
                if cc < 0:
                    continue
                if len([(i, j) for i in range(9) for j in range(9) if len(_tmp_p[i][j]) == 0]):
                    continue
                return find_dp(pp)
            return _tmp_p

        pp0 = find_dp(p)
        for i, j in to_complete:
            board[i][j] = str(pp0[i][j].pop())


board0 = [["5", "3", ".", ".", "7", ".", ".", ".", "."],
          ["6", ".", ".", "1", "9", "5", ".", ".", "."],
          [".", "9", "8", ".", ".", ".", ".", "6", "."],
          ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
          ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
          ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
          [".", "6", ".", ".", ".", ".", "2", "8", "."],
          [".", ".", ".", "4", "1", "9", ".", ".", "5"],
          [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
board1 = [[".", ".", "9", "7", "4", "8", ".", ".", "."],
          ["7", ".", ".", ".", ".", ".", ".", ".", "."],
          [".", "2", ".", "1", ".", "9", ".", ".", "."],
          [".", ".", "7", ".", ".", ".", "2", "4", "."],
          [".", "6", "4", ".", "1", ".", "5", "9", "."],
          [".", "9", "8", ".", ".", ".", "3", ".", "."],
          [".", ".", ".", "8", ".", "3", ".", "2", "."],
          [".", ".", ".", ".", ".", ".", ".", ".", "6"],
          [".", ".", ".", "2", "7", "5", "9", ".", "."]]
board2 = [[".", ".", ".", "2", ".", ".", ".", "6", "3"],
          ["3", ".", ".", ".", ".", "5", "4", ".", "1"],
          [".", ".", "1", ".", ".", "3", "9", "8", "."],
          [".", ".", ".", ".", ".", ".", ".", "9", "."],
          [".", ".", ".", "5", "3", "8", ".", ".", "."],
          [".", "3", ".", ".", ".", ".", ".", ".", "."],
          [".", "2", "6", "3", ".", ".", "5", ".", "."],
          ["5", ".", "3", "7", ".", ".", ".", ".", "8"],
          ["4", "7", ".", ".", ".", "1", ".", ".", "."]]
solution = Solution()
solution.solveSudoku(board0)
for each in board0:
    print(each)

print()
solution.solveSudoku(board1)
for each in board1:
    print(each)

print()
solution.solveSudoku(board2)
for each in board2:
    print(each)
